{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组&nbsp;<code>nums</code> ，数组中的元素 <strong>互不相同</strong> 。返回该数组所有可能的子集（幂集）。</p>\n",
    "\n",
    "<p>解集 <strong>不能</strong> 包含重复的子集。你可以按 <strong>任意顺序</strong> 返回解集。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0]\n",
    "<strong>输出：</strong>[[],[0]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10</code></li>\n",
    "\t<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>\n",
    "\t<li><code>nums</code> 中的所有元素 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 78&nbsp;题相同：&nbsp;<a href=\"https://leetcode-cn.com/problems/subsets/\">https://leetcode-cn.com/problems/subsets/</a></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [TVdhkn](https://leetcode.cn/problems/TVdhkn/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [TVdhkn](https://leetcode.cn/problems/TVdhkn/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def backtrack(idx, tmp):\n",
    "            res.append(tmp)\n",
    "            for i in range(idx, len(nums)):\n",
    "                backtrack(i + 1, tmp + [nums[i]])\n",
    "        backtrack(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        lists = []\n",
    "        lists.append([])\n",
    "        for i in range(1,len(nums)+1):\n",
    "            for j in combinations(nums,i):\n",
    "                lists.append(j)\n",
    "        return lists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # def dfs(res, nums):\n",
    "        #     if not nums:\n",
    "        #         return\n",
    "        #     if len(nums) == 1:\n",
    "        #         for i in range(len(res)):\n",
    "        #             tmp = res[i] + [nums[0]]\n",
    "        #             res.append(tmp)\n",
    "        #         return res\n",
    "        #     for i in range(len(res)):\n",
    "        #         t = res[i] + [nums[0]]\n",
    "        #         res.append(t)\n",
    "        #     return dfs(res, nums[1:])\n",
    "        # return dfs([[]], nums)\n",
    "\n",
    "        # n = len(nums)\n",
    "        # res = []\n",
    "        # def dfs(idx, tmp):\n",
    "        #     if idx == n:\n",
    "        #         res.append(tmp)\n",
    "        #         return\n",
    "        #     dfs(idx + 1, tmp + [nums[idx]])\n",
    "        #     dfs(idx + 1, tmp)\n",
    "        # dfs(0, [])\n",
    "        # return res\n",
    "\n",
    "        # res = [[]]\n",
    "        # for i in range(len(nums)):\n",
    "        #     for j in range(len(res)):\n",
    "        #         tmp = res[j] + [nums[i]]\n",
    "        #         res.append(tmp)\n",
    "        # return res\n",
    "\n",
    "        #########self的作用？，[:]的作用？pop的作用？\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        self.tmp = []\n",
    "        def dfs(idx):\n",
    "            if idx == n:\n",
    "                res.append(self.tmp[:])\n",
    "                print('res', res)\n",
    "                return\n",
    "            print('e', idx, self.tmp)\n",
    "            dfs(idx + 1)\n",
    "            print('t', idx, self.tmp)\n",
    "            self.tmp.append(nums[idx])\n",
    "            print('r', idx, self.tmp)\n",
    "            dfs(idx + 1)\n",
    "            print('11111111111')\n",
    "            self.tmp.pop()\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            for tmp in res[:]:\n",
    "                print(tmp, [num])\n",
    "                res.append(tmp+[num])\n",
    "                print(res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums, cache, layer, result):\n",
    "            print(cache, layer, result)\n",
    "            if layer == len(nums) - 1:\n",
    "                result.append(deepcopy(cache))\n",
    "                cache.append(nums[layer])\n",
    "                result.append(deepcopy(cache))\n",
    "                cache.pop()\n",
    "                return\n",
    "            dfs(nums, cache, layer + 1, result)\n",
    "            cache.append(nums[layer])\n",
    "            dfs(nums, cache, layer + 1, result)\n",
    "            cache.pop()\n",
    "            return\n",
    "\n",
    "        result = []\n",
    "        cache = []\n",
    "        dfs(nums, cache, 0, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef subsets(self, nums):\n",
    "\t\tans = [[]]\n",
    "\t\tfor num in nums:\n",
    "\t\t\tcur = [lst + [num] for lst in ans]\n",
    "\t\t\tans.extend(cur)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(i):\n",
    "            if i==len(nums):\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            # 不选\n",
    "            dfs(i+1)\n",
    "            # 选\n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        ans=list()\n",
    "        path=[]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        daan=[]\n",
    "        n=len(nums)\n",
    "        x=0\n",
    "        while n > 0 :\n",
    "            x=x*2+1\n",
    "            n-=1\n",
    "            '''\n",
    "            转二进制\n",
    "            '''\n",
    "        while x>=0 :\n",
    "            a=x\n",
    "            n = len(nums)\n",
    "            l=[]\n",
    "            for i in range (n):\n",
    "                if (((a>>i) & 1)==1):\n",
    "                    l.append(nums[i])\n",
    "            x-=1\n",
    "            daan.append(l)\n",
    "        return daan\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        for pos in range(2**n):\n",
    "            tmp = []\n",
    "            i = 0\n",
    "            while (pos!=0):\n",
    "                if pos%2 == 1:\n",
    "                    tmp.append(nums[i])\n",
    "                i = i+1\n",
    "                pos = pos//2\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [[]] \n",
    "        for num in nums:\n",
    "            ans += [lst+[num] for lst in ans] \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[[]]\n",
    "        for i in nums:\n",
    "            res+=[[i]+r for r in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        output = []\n",
    "        n = len(nums)\n",
    "        #binary\n",
    "        for i in range(2**n):\n",
    "            temp = bin(i)[2:]\n",
    "            temp = temp.rjust(n, '0')\n",
    "            current_list = []\n",
    "            for j in range(len(temp)):\n",
    "                if temp[j]!='0':\n",
    "                    current_list.append(nums[j])\n",
    "            output.append(current_list)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # def generate_subsets(nums):\n",
    "        def backtrack(start, subset):\n",
    "            # 当前子集是一个解\n",
    "            result.append(subset[:])\n",
    "\n",
    "            # 从start开始向子集添加元素\n",
    "            for i in range(start, len(nums)):\n",
    "                subset.append(nums[i])\n",
    "                # 递归生成子集\n",
    "                backtrack(i + 1, subset)\n",
    "                # 回溯，将最后一个元素移除，以便尝试下一个元素\n",
    "                subset.pop()\n",
    "\n",
    "        result = []\n",
    "        backtrack(0, [])\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        path=[]\n",
    "        n=len(nums)\n",
    "\n",
    "        def backtrack(startidx):\n",
    "            res.append(path[:])\n",
    "\n",
    "            if startidx==n:\n",
    "                return\n",
    "\n",
    "            for i in range(startidx,n):\n",
    "                path.append(nums[i])\n",
    "                backtrack(i+1)\n",
    "                path.pop()\n",
    "            \n",
    "        backtrack(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def dfs(depth):\n",
    "            res.append(path[:])\n",
    "            if depth == n:\n",
    "                return\n",
    "            for i in range(depth, n):\n",
    "                path.append(nums[i])\n",
    "                dfs(i+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        size = len(nums)\n",
    "        dp = []\n",
    "        for i in range(2**size):\n",
    "            count = list(bin(i)[2:])\n",
    "            temp = []\n",
    "            for j, x in enumerate(count[::-1]):\n",
    "                if x == '1':\n",
    "                    temp.append(nums[j])\n",
    "            dp.append(temp)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        sub = []\n",
    "\n",
    "        def dfs(depth):\n",
    "            ans.append(sub[:])\n",
    "            for i in range(depth, len(nums)):\n",
    "                sub.append(nums[i])\n",
    "                dfs(i+1)\n",
    "                sub.pop()\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if nums == []:\n",
    "            return []\n",
    "        temp = [[],[nums[0]]]\n",
    "        temp2 = []\n",
    "        for i in nums[1:]:\n",
    "            for j in temp:\n",
    "                temp2.append(j)\n",
    "                temp2.append(j + [i])\n",
    "            temp = temp2\n",
    "            temp2 = []\n",
    "        \n",
    "        return temp \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def dfs(i, tmp):\n",
    "            res.append(tmp)\n",
    "            for j in range(i, n):\n",
    "                dfs(j + 1, tmp + [nums[j]])\n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        print(n)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            # 终止逻辑\n",
    "            if i == n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            # 单层递归逻辑\n",
    "            # 不选第i个元素\n",
    "            i += 1\n",
    "            dfs(i)\n",
    "            i -= 1 # 恢复现场\n",
    "\n",
    "            # 选第i个元素\n",
    "            path.append(nums[i])\n",
    "            i += 1\n",
    "            dfs(i) # 继续 深度优先搜索\n",
    "            i -= 1 # 恢复现场\n",
    "            path.pop() # 恢复现场\n",
    "        \n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        if len(nums)==0:\n",
    "            return res\n",
    "\n",
    "        subset=[]\n",
    "        \n",
    "        def dfs(idx):\n",
    "            if idx==len(nums):\n",
    "                res.append(subset.copy())\n",
    "                return\n",
    "\n",
    "            subset.append(nums[idx])\n",
    "            dfs(idx+1)\n",
    "            subset.pop()\n",
    "\n",
    "            dfs(idx+1)\n",
    "\n",
    "        dfs(0)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i:int) -> None:\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return \n",
    "            dfs(i+1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        def dfs(index,n,path):\n",
    "            res.append(path.copy())\n",
    "            if index==n:\n",
    "                return\n",
    "            for j in range(index,n):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1,n,path)\n",
    "                path.pop()\n",
    "        dfs(0,len(nums),[])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        for i in range(1 << n):\n",
    "            t = []\n",
    "            for j in range(i.bit_length() + 1):\n",
    "                if i >> j & 1:\n",
    "                    t.append(nums[j])\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(idx):\n",
    "            if idx == len(nums):\n",
    "                ans.append(tmp[:])\n",
    "                return\n",
    "            \n",
    "            tmp.append(nums[idx])\n",
    "            dfs(idx + 1)\n",
    "            tmp.pop()\n",
    "            dfs(idx + 1)\n",
    "\n",
    "        tmp = []\n",
    "        ans = []\n",
    "        dfs(0) \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if len(nums) == 0:\n",
    "            return [[]] \n",
    "        ##\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        def backtrack(i):\n",
    "            if i == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            ##\n",
    "            path.append(nums[i])\n",
    "            backtrack(i+1)\n",
    "            path.pop()\n",
    "            ##\n",
    "            backtrack(i+1)\n",
    "            ##\n",
    "        backtrack(0)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def dfs(nums, pos, path, res):\n",
    "            \n",
    "            if pos == len(nums):\n",
    "                return \n",
    "            for i in range(pos, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                res.append(path.copy())\n",
    "                dfs(nums, i+1, path, res)\n",
    "                path.pop()\n",
    "        res = []\n",
    "        dfs(nums, 0, [], res)\n",
    "        res.append([])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:      \n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs (i:int):\n",
    "            ans.append(path.copy())\n",
    "            for j in range (i,len(nums)):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1)\n",
    "                del path[len(path)-1]\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        import copy\n",
    "        res = [[]]\n",
    "        for i in range(len(nums)):\n",
    "            temp = copy.deepcopy(res)\n",
    "            for item in temp:\n",
    "                item.append(nums[i])\n",
    "                res.append(item)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.res=[]\n",
    "        self.backtrack(nums,0,[])\n",
    "        return self.res\n",
    "        \n",
    "    def backtrack(self,nums,start,track):\n",
    "        self.res.append(track[:])\n",
    "        for i in range(start,len(nums)):\n",
    "            track.append(nums[i])\n",
    "            self.backtrack(nums,i+1,track)\n",
    "            track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def test(first, path):\n",
    "            re.append(path[:])\n",
    "            for i in range(first, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                test(i+1, path)\n",
    "                path.pop()\n",
    "\n",
    "        re = []\n",
    "        test(0, [])\n",
    "        return re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def dfs(i, tmp):\n",
    "            res.append(tmp)\n",
    "            for j in range(i, n):\n",
    "                dfs(j + 1, tmp + [nums[j]])\n",
    "        dfs(0, [])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        for i in range(1 << len(nums)):\n",
    "            list = []\n",
    "            for j in range(len(nums)):\n",
    "                if ((i >> j) & 1 == 1):\n",
    "                    list.append(nums[j])\n",
    "            ans.append(list)\n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "\n",
    "        def dfs(i):\n",
    "            if i==n:\n",
    "                ans.append(path.copy())\n",
    "                return \n",
    "            dfs(i+1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        track = []\n",
    "        res = []\n",
    "        self.backtrack(nums,0,track,res)\n",
    "        return res\n",
    "    def backtrack(self,nums: List[int],start:int,track: List[int],res: List[int]) ->None:\n",
    "        res.append(track[:])\n",
    "        for i in range(start, len(nums)):\n",
    "            track.append(nums[i])\n",
    "            self.backtrack(nums,i+1,track,res)\n",
    "            track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return nums\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            cur_len = len(res)\n",
    "            for i in range(cur_len):\n",
    "                res.append(res[i] + [num])\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        track = []\n",
    "        self.backtrack(nums, 0,track)\n",
    "        return self.res\n",
    "    def backtrack(self,nums: List[int],start:int ,track:List[int]) ->None:\n",
    "        self.res.append(track[:])\n",
    "        for i in range(start, len(nums)):\n",
    "            track.append(nums[i])\n",
    "            self.backtrack(nums,i+1, track)\n",
    "            track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        l=[]\n",
    "        for n in range(0,len(nums)+1):\n",
    "            for i in combinations(nums, n):\n",
    "                l.append(i)\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [] #存结果\n",
    "        n = len(nums)\n",
    "\n",
    "        path = [] #存过程\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            dfs(i + 1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans\n",
    "                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i:int) -> None:\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return \n",
    "            dfs(i+1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        if not nums:\n",
    "            return []\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        def backtrack(nums, begin, k, path):\n",
    "            if len(path) == k:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(begin, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtrack(nums, i+1, k, path)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        for i in range(n+1):\n",
    "            backtrack(nums,0 , i, [])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res, n = [], len(nums)\n",
    "\n",
    "        def dfs(start, path):\n",
    "            res.append(path)\n",
    "            for i in range(start, n):\n",
    "                dfs(i+1, path+[nums[i]])\n",
    "        \n",
    "        dfs(0, [])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-san-zha-24031/bao-li-sou-96f79/hui-su-sua-56e11/\n",
    "# 元素无重不复选 子集问题\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(nums, 0)\n",
    "\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, nums, start):\n",
    "        # 终止条件要做的事。前序位置，每一个节点都是一个子集\n",
    "        self.res.append(list(self.track))\n",
    "\n",
    "        # for 选择 in 选择列表：\n",
    "        for i in range(start, len(nums)):\n",
    "            # 做选择\n",
    "            self.track.append(nums[i])\n",
    "            # 回溯\n",
    "            self.backtrack(nums, i + 1)\n",
    "            # 撤销选择\n",
    "            self.track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = [[]]\n",
    "        for each in nums:\n",
    "            size = len(result)\n",
    "            for i in range(size):\n",
    "                temp = result[i].copy()\n",
    "                temp.append(each)\n",
    "                result.append(temp)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []\n",
    "        cur_list = []\n",
    "        self.helper(result, cur_list, nums, 0)\n",
    "        return result\n",
    "\n",
    "    def helper(self, result, cur_list, arr, pos):\n",
    "        result.append(cur_list.copy())\n",
    "        for i in range(pos, len(arr)):\n",
    "            cur_list.append(arr[i])\n",
    "            self.helper(result, cur_list, arr, i + 1)\n",
    "            cur_list.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []\n",
    "\n",
    "        def dfs(l1, l2):\n",
    "            nonlocal result\n",
    "            l3 = []\n",
    "            for i in l2:\n",
    "                l3.append(i)\n",
    "            result.append(l3)\n",
    "            for i in range(len(l1)):\n",
    "                dfs(l1[i + 1:], l2 + [l1[i]])\n",
    "\n",
    "        dfs(nums, [])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 注意：python 代码由 chatGPT\\U0001f916 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。\n",
    "# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "        self.track = []\n",
    "\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.backtrack(nums, 0)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, nums: List[int], start: int) -> None:\n",
    "        self.res.append(list(self.track))\n",
    "        for i in range(start, len(nums)):\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums, i + 1)\n",
    "            self.track.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = []\n",
    "        nums.sort()\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            #不选\n",
    "            dfs(i + 1)\n",
    "            #选\n",
    "            path.append(nums[i])\n",
    "            dfs(i + 1)\n",
    "            path.pop()\n",
    "            \n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ret = []\n",
    "        n = len(nums)\n",
    "        def help(index, temp):\n",
    "            ret.append(temp)\n",
    "            for i in range(index, n):\n",
    "                help(i + 1, temp + [nums[i]])\n",
    "        help(0, [])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "\n",
    "        for num in nums:\n",
    "            cur_len = len(res)\n",
    "            for i in range(cur_len):\n",
    "                res.append(res[i]+ [num])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrace(nums, path, result, start):\n",
    "            result.append(path[:])\n",
    "\n",
    "            if start > len(nums):\n",
    "                return\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtrace(nums, path, result, i+1)\n",
    "                path.pop()\n",
    "\n",
    "        path = []\n",
    "        result = []\n",
    "        backtrace(nums, path, result, 0)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(index):\n",
    "            if n == index:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            path.append(nums[index])\n",
    "            dfs(index + 1)\n",
    "            path.pop()\n",
    "            dfs(index + 1)\n",
    "\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        # path = []\n",
    "        # def dfs(i):  \n",
    "        #     if i == n:\n",
    "        #         ans.append(path.copy())\n",
    "        #         return\n",
    "        #     dfs(i+1)\n",
    "        #     path.append(nums[i])\n",
    "        #     dfs(i+1)\n",
    "        #     path.pop()\n",
    "        # dfs(0)\n",
    "        for i in range(len(nums)+1):\n",
    "            ans.extend(combinations(nums,i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [[]]\n",
    "        for num in nums:\n",
    "            ans += [lst + [num] for lst in ans]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.res = [[]]\n",
    "        trace = []\n",
    "        for i in range(len(nums)):\n",
    "            self.travel(trace, nums, i)\n",
    "        return self.res\n",
    "    \n",
    "    def travel(self, trace, nums, pos):\n",
    "        trace.append(nums[pos])\n",
    "        curRes = [val for val in trace]\n",
    "        self.res.append(curRes)\n",
    "        for i in range(pos + 1, len(nums)):\n",
    "            self.travel(trace, nums, i)\n",
    "        trace.pop()\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "      def backtrace(start,temp):\n",
    "        res.append(temp[:])\n",
    "        for i in range(start,len(nums)):\n",
    "          temp.append(nums[i])\n",
    "          backtrace(i+1,temp)\n",
    "          temp.pop()\n",
    "        \n",
    "      res=[]\n",
    "      backtrace(0,[])\n",
    "      return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [[]]\n",
    "        self.dfs(nums, 0, [], ans)\n",
    "        # for a in nums:\n",
    "        #     seqs = ans[1:]\n",
    "        #     for b in seqs:\n",
    "        #         c = [*b, a]\n",
    "        #         ans.append(c)\n",
    "        #     ans.append([a])\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, nums, cur, trace, ans):\n",
    "        if cur == len(nums):\n",
    "            return\n",
    "        trace.append(nums[cur])\n",
    "        ans.append(trace[:])\n",
    "        self.dfs(nums, cur+1, trace, ans)\n",
    "        trace.pop()\n",
    "        self.dfs(nums, cur+1, trace, ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(1 << n):\n",
    "            t = []\n",
    "            for j in range(n):\n",
    "                if i >> j & 1:\n",
    "                    t.append(nums[j])\n",
    "            ans.append(t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        # res = []\n",
    "\n",
    "        # for i in range(len(nums)):\n",
    "        #     res.extend(itertools.combinations(nums, i))\n",
    "        # res.extend([nums])\n",
    "        # return res\n",
    "        \n",
    "        n = len(nums)\n",
    "        mask = 0\n",
    "        ans = []\n",
    "        while mask < (1 << n):\n",
    "            tmp = []\n",
    "            for i in range(n):\n",
    "                if (mask & (1 << i)) != 0:\n",
    "                    tmp.append(nums[i])\n",
    "            ans.append(tmp)\n",
    "\n",
    "            mask += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        n = len(nums)\n",
    "        path = []\n",
    "        def dfs(curr):\n",
    "            if curr == n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            path.append(nums[curr])\n",
    "            dfs(curr + 1)\n",
    "            path.pop()\n",
    "            dfs(curr + 1)\n",
    "        dfs(0)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        res, path = [], []\n",
    "        \n",
    "        def dfs(idx, path):\n",
    "            res.append(path[:])\n",
    "            if len(nums) == idx:\n",
    "                return\n",
    "        \n",
    "            for i in range(idx, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(i+1, path)\n",
    "                path.pop()\n",
    "        dfs(0, path)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        self.ret = []\n",
    "\n",
    "        def helper(i, nums, sub):\n",
    "            if i == len(nums):\n",
    "                self.ret.append(sub)\n",
    "                return\n",
    "            helper(i+1, nums, sub)\n",
    "            helper(i+1, nums, sub + [nums[i]])\n",
    "\n",
    "        helper(0, nums, [])\n",
    "        return self.ret\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = []\n",
    "        def dfs(i):\n",
    "            \n",
    "            if i == n:\n",
    "                ans.append(path.copy())\n",
    "                return\n",
    "            dfs(i+1)\n",
    "            path.append(nums[i])\n",
    "            dfs(i+1)\n",
    "            path.pop()\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        t = []\n",
    "        ans = []\n",
    "        def dfs(cur: int) -> None:\n",
    "            if cur == len(nums): \n",
    "                ans.append(t.copy())\n",
    "                return\n",
    "            t.append(nums[cur])\n",
    "            dfs(cur + 1)\n",
    "            t.pop()\n",
    "            dfs(cur + 1)\n",
    "            return\n",
    "        dfs(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsets(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = [[]]\n",
    "        for a in nums:\n",
    "            seqs = ans[1:]\n",
    "            for b in seqs:\n",
    "                c = [*b, a]\n",
    "                ans.append(c)\n",
    "            ans.append([a])\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
